package org.example.myleet.p1219;

public class Solution {

    private static final int[][] DIRS = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    private int maxSum;
    private int m;
    private int n;

    public int getMaximumGold(int[][] grid) {
        maxSum = 0;
        m = grid.length;
        n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] > 0) {
                    backTrack(grid, visited, 0, i, j);
                }
            }
        }
        return maxSum;
    }

    private void backTrack(int[][] grid, boolean[][] visited, int sum, int row, int col) {
        sum += grid[row][col];
        if (sum > maxSum) {
            maxSum = sum;
        }
        visited[row][col] = true;
        for (int i = 0; i < 4; ++i) {
            int[] dir = DIRS[i];
            int r = row + dir[0];
            int c = col + dir[1];
            if (0 <= r && r < m && 0 <= c && c < n && !visited[r][c] && 0 < grid[r][c]) {
                backTrack(grid, visited, sum, r, c);
            }
        }
        visited[row][col] = false;
    }
}
